#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* computeNext(char* word){
    int* next = malloc(strlen(word)*sizeof(int));
    int i = 0;
    next[0] = 0;
    for(int j=1;j<strlen(word);j++){
        while (i>0 && word[i]!=word[j]){
            i = next[i-1];
        }
        if(word[i]==word[j]){
            i++;
        }
        next[j] = i;
    }
    return next;
}

int KMP(char* text,char* word){
    int* next = computeNext(word);
    int w=0;
    int t=0;
    for(;t<strlen(text);t++){
        if(word[w]=='\0'){return t;}
        while (w>0 && text[t]!=word[w]){
            w = next[w-1];
        }
        if(text[t]==word[w]){
            w++;
        }
    }
    return 0;
}

int main(){
    char* text = "abacwabdwdabacwababdwadfwcaw";
    char* word = "abacwabab";
    int* next = computeNext(word);
    for(int x=0;x<strlen(word);x++){
        printf("%c ",word[x]);
    }
    printf("\n");
    for(int x=0;x<strlen(word);x++){
        printf("%d ",next[x]);
    }
    printf("\n");

    int r = KMP(text,word);
    printf("%d",r);

    return 0;
}